Load distribution or load spreading is a method by which bandwidth is more effectively utilized and overall performance is improved in a network. Most automated load distribution and load spreading techniques deployed today operate with only a very local view, these load distribution and load spreading techniques only consider the number of next hops on the shortest path to a given destination and do not consider the overall distribution of traffic in the network.
Equal cost multi-path (ECMP) is a common strategy for load spreading of unicast traffic in routed networks that can be utilized where the decision as to how to forward a packet to a given destination can resolve to any of multiple “equal cost” next hops, which tied for being on the shortest path when running database calculations. ECMP can be used in conjunction with most unicast routing protocols and nodes equipped with the required supporting data plane hardware. It relies on a per hop decision that is local to a single router and assumes promiscuous receipt and a complete forwarding table at every intermediate node. Using ECMP at any given node in a network, the load is divided pseudo-evenly across the set of equal cost next hops. This process is implemented independently at each hop of the network where more than one path to a given destination exists.
In many implementations, when the presence of multiple equal cost next hops is encountered, each packet is inspected for a source of entropy such as an Internet Protocol (IP) header and a hash of header information modulo of the number of paths is used to select the next hop for the particular packet and will select the same next hop for all packets in a given “flow”. For highly aggregated traffic, this method will on average distribute the load evenly in regular topologies (i.e., symmetric topologies) and does offer some improvement in less regular topologies.
Current approaches to data center design utilize what are known as Clos or “Fat Tree” networks. These networks are highly regular and are noted for utilizing arrays of switching nodes combined with very dense meshing in order to scale bandwidth. One of the complications of load spreading on a fat tree network is that the number of paths increases as the square of the connectedness. ECMP can be a good fit in such applications but ECMP based load spreading is dependent on the symmetric regularity of the switching hierarchy to achieve efficiency and near perfect re-randomization of flow to next hop assignment at each hop. A further complication with ECMP is that it cannot be applied to Ethernet without separating the treatment of multicast from unicast as per hop ECMP cannot be applied to multicast traffic. The net result of this is that race conditions can exist between unicast forwarding and the multicast flooding of unknown packets such that out of order delivery can occur in a stable network. Therefore it is desirable to find an alternative to ECMP for Ethernet that is applicable to highly meshed regular networks and where degradation of the traffic distribution is minimized by failures in the network.